package com.heima.leetcode.practice;

import java.util.concurrent.ThreadLocalRandom;

/**
 * leetcode 215. 数组中的第K个最大元素
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/13 20:48
 */
public class E215 {
    /*
       6 5 4 3 2 1
       0 1 2 3 4 5
     */

    /**
     * 数组中的第K个最大元素
     * @param nums 数组
     * @param k 第k大的
     * @return 第k大的元素
     */
    public int findKthLargest(int[] nums, int k) {
        int rank = nums.length - k; // 转化为排名
        return quickSelect(nums, 0, nums.length - 1, rank);
    }

    /**
     * 快速选择算法，核心思想是快速排序的分区思想O(n)
     * @param arr 指定数组
     * @param begin 开始下标（包含）
     * @param end 结束下标（包含）
     * @param k 排名从0开始
     * @return 第k名的元素
     */
    private static int quickSelect(int[] arr, int begin, int end, int k) {
        int pivot = partition(arr, begin, end);
        if (pivot == k){
            return arr[pivot];
        } else if (pivot < k) {
            return quickSelect(arr, pivot + 1, end, k);
        } else {
            return quickSelect(arr, begin, pivot - 1, k);
        }
    }

    private static int partition(int[] arr, int begin, int end) {
        int randomIndex = ThreadLocalRandom.current().nextInt(end - begin + 1) + begin;
        swap(arr, begin, randomIndex);
        int pivot = arr[begin];
        int le = end;
        int ge = begin + 1;
        while (ge <= le){
            while (ge <= le && arr[le] > pivot){
                le--;
            }
            while (ge <= le && arr[ge] < pivot){
                ge++;
            }
            if (ge <= le){
                if (arr[ge] != arr[le]) {
                    swap(arr, ge, le);
                }
                ge++;
                le--;
            }
        }
        swap(arr, begin, le);
        return le;
    }

    private static void swap(int[] arr, int begin, int end) {
        int temp = arr[begin];
        arr[begin] = arr[end];
        arr[end] = temp;
    }
}
